Target tracking is the process of calculating the path or track of a moving object by monitoring its current position and using the data obtained from this monitoring to project its future position. An example of target tracking is the process of air traffic control where radar stations send out signals and receive reflections (hits) from on-coming planes (targets), thereby determining the flight path (track) of the plane.
In most practical applications, it is rare that a single target needs to be tracked. More usually, multiple targets are moving in relatively close proximity to each other and the path of each must be distinguished and determined. In air traffic control, this is most evident at airports where multiple planes are either on an approach or take-off flight path in the airspace surrounding the airport.
A significant problem in multiple target tracking is the hit-to-track data association. A precise definition of a "hit" is a received signal from a target or background clutter which provides positional information. Generally, in calculating a track (that is, the path taken by the target), a prediction is made as to point at which the next hit against the target will be made. A region, known as an "extension gate" is defined about that point. FIG. 1 shows the extension gate (100) for track J (30). Hits within the extension gate of a target are candidates for being used in further calculation of the track. Where there are multiple targets, closely spaced, a hit against second target may also be located in the extension gate of the first target. In FIG. 1, this is illustrated by hit 4 which is associated with track k (4)) but lies within track j's extension gate (100). If that hit is associated with the first target (i.e., incorrectly associated with the first track), the calculated track that results could diverge from the actual path of the target. In the worst case, the calculated track can terminate. Thus, where multiple signals are being received from multiple targets, it is imperative that each received hit be associated with the correct target and/or be identified as background clutter (and therefore be discounted in the track calculations).
Probabilistic Data Association
Prior methods for this data association problem include various optimal and suboptimal two-dimensional assignment algorithms which make hit-to-track associations.
The idea of Probabilistic Data Association (PDA) was first proposed by Bar-Shalom and Tse, "Tracking in a Cluttered Environment with Probabilistic Data Association," Automatica, Vol. 11, September 1975, pps. 451-60. PDA is a method of associating hits detected in the current readout of the sensor, or scan, with current tracks using a probabilistic score. A score is a measure of the goodness of fit of the hit-to-track association. Once the score for each hit is calculated, the tracks are updated with a weighted sum of the hits, where the weights are the calculated probabilities. This was thought to be a very good method for tracking targets in dense clutter without having the large processor and memory usage needed for multiple hypothesis tracking. This idea was extended to tracking maneuvering targets.
The PDA approach assumes all hits in a particular target's extension gate all either are a hit from the target or are random clutter points. If another target hit is persistently in this particular target extension gate, the probability calculation will be wrong and poor tracking will result.
To account for the problem of two or more targets in the same extension gate, a method was developed which assigned a weight for the reasonable hits and used a weighted centroid of those hits to update the track. This method of weighting the hits is known as Joint Probabilistic Data Association (JPDA). (JPDA is discussed in T. E. Fortmann, Y. Bar-Shalom, and M. Scheffe, "Multi-Target Tracking Using Joint Probabilistic Data Association " Proc. of the IEEE Conference on Decision and Control, Vol 2 December 1980 pps 807-12 and "Sonar Tracking of Multiple Targets Using Joint Probabilistic Data Association," IEEE Journal of Oceanic Research, Vol. OE-8, July 1983, pps. 173-184.)
Briefly, in JPDA, a joint probability is calculated over all targets and hits. The joint probability is the probability of all the individual events combined as a joint event. Thus, JPDA includes the possibility of multiple hits in one track extension gate coming from other targets. This method was later extended to include the radial velocity measurement from doppler radars (V. Nargarajan, R. N. Sharma, and M. R. Chidambara, "An Algorithm for Tracking a Maneuvering Target in Clutter," IEEE Transactions on Aerospace and Electronic Systems, Vol. AES-20, September 1984, pp. 560-73, corrected, ibid., December 1984, Vol. AES-20, p. 844.)
While this JPDA method worked for its intended purpose, it required a prohibitive amount of processor time in calculating the joint probabilities. This issue was addressed with a distributed processing solution (See, K. C. Change and Bar-Shalom, "Distributed Adaptive Estimation with Probabilistic Data Association," Automatica, Vol. 25, No. 3, 1989, pps. 359-69) and fast algorithms using some matrix manipulations (See S. D. O'Neil and M. F. Bridgland, "Fast Algorithms for Joint Probabilistic Data Association," Procedure of the SDI Panels on Tracking, No. 1/1991, April 1991, pps. 3-102-3-122). However, these approaches still had problems in terms of 1) the time it took to perform the calculation, 2) the size of computer memory required and, in general, 3) implementation.
In Multitarget-Multisensor Tracking: Advanced Applications, Vol. 1, Yaakov Bar-Shalom, editor, 1990, Chapter 1, Robert Fitzgerald proposed an ad hoc method of calculating a probability that approximates the JPDA calculation. The following section briefly describes the JPDA Method (or "Filter"). A more detailed derivation of the JPDA filter can be found in Yaakov Bar-Shalom and Thomas E. Fortmann, Tracking and Data Association, 1988. JPDA Method
Optimal JPDA Filter
The difference between the PDA filter and the optimal JPDA filter is the method of calculating the probability weights
In the case of the PDA filter, the weights are calculated independently track by track. For each track, PDA calculates the probability of each hit in the track's extension gate using Bayes rule. The probability that the target was not detected can also be calculated using a uniform distribution or a parametric Poisson distribution for the false or clutter hits. This method does not consider any other hits in the track extension gate to be from another target.
The JPDA filter's probability calculations do consider other hits coming from other targets and are quite complex and computationally intensive. In JPDA, the joint probability is calculated by first calculating the probability of all possible feasible joint events, where one possible joint event at time k is denoted as .theta.(k). A feasible joint event is a non-conflicting association of current targets with hits, while the remaining unassociated hits would be declared as clutter points. This non-conflicting association is based on the requirement that no two tracks are associated with the same hit. A feasible joint event does not have to associate all tracks to a hit. This would correspond to a probability of detection P.sub.D Of less than one.
With reference to FIG. 1, an example of a feasible joint event would be as follows. Suppose there are current tracks h, i,j,k,,1 (represented in FIG. 1 as 10, 20, 30, 40 and 50 respectively) and present hits (1,2,3,4,5,6). In FIG. 1, the "x's" indicate the positions of hits, while the dotted lines indicate positions of the track extension point.
In this situation, a feasible joint event would be described by the following equation: EQU .theta.(k)=(i,3) (j,2)(h,6)(l,1)(clutter hits 4,5) (1)
This joint event is the event which occurs when tracks i, j, h, and l are associated with hits 3, 2, 6, and 1, track k was not detected on this scan, and hits 4 and 5 were clutter.
In the JPDA filter all possible joint events must be constructed and their probabilities calculated. The probability of an event given the history of hits (Z.sup.k) up until time k is given by ##EQU1## where c is a normalizing constant and Z(K) is the set of hits at time k. The Probability Density Function (PDF) on the right hand side of the equation is the density function when evaluated for the present set of hits. Given the joint event .theta.(k) is the correct hypothesis of assignments, and given the past history of hits, the PDF is given by ##EQU2## where z.sub.j (k) is the j-th hit in Z(k), and .theta..sub.j (k) is the assignment of the j-th hit to either a current track or clutter. The PDF of each hit is given by ##EQU3## where V is the volume of the extension gate and N[] is the normal density function with zero mean and covariance equal to the covariance matrix of v.sub.j (k) for the track to which hit j is assigned. Therefore, ##EQU4## where .tau..sub.j is equal to one if the j-th hit is assigned to a track and zero otherwise, and .phi. is the number of points determined to be clutter rather than points along a track. The next step is to calculate the prior probability P{.theta.(k)}. This can be done by writing the prior probability as ##EQU5## where .delta. indicates which tracks have been assigned to present hits. The first factor, P{.theta.(k)/.delta., .phi.} can be found by noting that the number of targets detected in the joint event .theta.(k) is m-.phi., where m is the total number of hits. The number of joint events with the same set of targets detected is the permutation of m hits taken as m-.phi.. Assuming that each event is equally likely, ##EQU6## The last factor P{.delta., .phi.} is given by ##EQU7## where P.sup.t.sub.D is the probability of detection for track t, .delta..sub.t is a binary indicator that track t has been assigned a hit in the joint event, .theta.(t) and u.sub.t (.phi.) is the prior probability mass function for the number of clutter hits in this joint event. The binary indicator .delta..sub.t is a one if track t is assigned a hit and zero if not. The nonparametric JPDA, which is used here, assumes a diffuse prior probability so that u.sub.f (.phi.) will cancel from each term in the 1/c normalizing factor. Since m! is in each of the terms, it will also cancel in the normalizing factor. Combining equations (8-13) into equation (7), the probability of the joint event, i s given by ##EQU8## From the law of total probability, the weighting factor, or probability of track t being associated with hit j, is the sum of the probabilities of all joint events in which track t is 15 associated with hit j. This can be written as ##EQU9## where .omega.(.theta.(k)) is a binary variable indicating whether track t is associated with hit j in .theta.(k). The normalizing constant c is the sum over all joint events of the numerator of P{.theta.(k)/Z.sup.k }.